Theory of Computation
Q111.
Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below. The missing arcs in the DFA areQ113.
Let w be any string of length n in {0, 1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?Q114.
A deterministic finite automation (DFA)D with alphabet \Sigma= {a,b} is given below Which of the following finite state machines is a valid minimal DFA which accepts the same language as D?Q117.
Definition of a language L with alphabet {a} is given as following L={a^{nk} |k > 0, and n is a positive integer constant} What is the minimum number of states needed in a DFA to recognize L?Q118.
Given the following state table of an FSM with two states A and B, one input and one output: If the initial state is A = 0, B=0, what is the minimum length of an input string which will take the machine to the state A=0, B=1 with Output=1?Q119.
If the final states and non-final states in the DFA below are interchanged, then which of the following languages over the alphabet {a,b} will be accepted by the new DFA?Q120.
Let N be an NFA with n states and let M be the minimized DFA with m states recognizing the same language. Which of the following in NECESSARILY true?